package graphes;

import java.util.ArrayList;
import java.util.List;

public class Dijkstra {
	public static List<Arc> AlgoDijkstra(Graphe G, Noeud racine, Noeud fin) throws IndexOutOfBoundsException {
		List<Noeud> noeuds = G.getNoeuds();
		int nbNoeud = noeuds.size();
		double poids[] = new double[nbNoeud];
		Arc chemin[] = new Arc[nbNoeud];
		boolean marque[] = new boolean[nbNoeud];
		for (int i = 0; i < nbNoeud; i++) {
			poids[i] = Double.POSITIVE_INFINITY;
			marque[i] = false;
		}
		poids[racine.getNumero()-1] = 0;
		chemin[racine.getNumero()-1] = null;
		Noeud n = racine;
		while (n != fin) {
			marque[n.getNumero()-1] = true;
			List<Arc> listeArc = n.getListeArcsSortant();
			for (Arc arc : listeArc) {
				if (poids[arc.getFin().getNumero()-1] > poids[n.getNumero()-1]
						+ arc.getPoids()) {
					poids[arc.getFin().getNumero()-1] = poids[n.getNumero()-1]
							+ arc.getPoids();
					chemin[arc.getFin().getNumero()-1] = arc;
				}
			}
			try{
				n = minNoeud(marque, poids, noeuds);
			}
			catch (IndexOutOfBoundsException ex){
				throw ex;
			}
		}
		int numero = fin.getNumero()-1;
		List<Arc> renvoi = new ArrayList<Arc>();
		while (chemin[numero] != null) {
			renvoi.add(0, chemin[numero]);
			numero = chemin[numero].getDebut().getNumero()-1;
		}
		return renvoi;
	}

	public static Noeud minNoeud(boolean marque[], double poids[],
			List<Noeud> noeuds) throws IndexOutOfBoundsException {
		Noeud renvoi = null;
		int idxMin = 0;
		while (marque[idxMin] == true) {
			idxMin++;
		}
		for (int i = idxMin + 1; i < poids.length; i++) {
			if (marque[i] == false && poids[i] < poids[idxMin]) {
				idxMin = i;
			}
		}
		for (int j = 0; j < noeuds.size(); j++) {
			try {
				if (noeuds.get(j).getNumero()-1 == idxMin) {
					return noeuds.get(j);
				}
			} catch (IndexOutOfBoundsException ex) {
				throw ex;
			}
		}
		return renvoi;
	}
}